/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <vector>
#include <stack>
#include <utility>
using namespace std;
class Solution {
    vector<int> ans;
    stack<pair<TreeNode *, int> > s;
public:
    vector<int> inorderTraversal(TreeNode *root) {
        ans.clear();
        if (root==NULL) return ans;
        s.push(make_pair(root, 0));
        while (!s.empty()) {
            TreeNode * &st=s.top().first;
            int &choice=s.top().second;
            if (choice==0) {
                if (st->left!=NULL) s.push(make_pair(st->left, 0));
                choice=1;
                continue;
            }
            if (choice==1) {
                ans.push_back(st->val);
                choice=2;
                continue;
            }
            if (choice==2) {
                if (st->right!=NULL) s.push(make_pair(st->right, 0));
                choice=3;
                continue;
            }
            if (choice==3) {
                s.pop();
                continue;
            }
        }
        return ans;
    }
};
